
//leetcode
//https://leetcode.cn/problems/find-longest-subarray-lcci/description/

//前缀和,思维转换,哈希表


class Solution
{
public:
    vector<string> findLongestSubarray(vector<string> &array)
    {
        int n = array.size(), s[n + 1]; // 前缀和
        s[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            int t;
            //s[i + 1] = s[i] + (array[i][0] >> 6 & 1) * 2 - 1;
            if(array[i][0] >= '0' && array[i][0] <= '9') t = -1;
            else t = 1;
            s[i + 1] = s[i] + t;

        }


        int begin = 0, end = 0; // 符合要求的子数组 [begin,end)
        unordered_map<int, int> first;
        for (int i = 0; i <= n; ++i)
        {
            auto it = first.find(s[i]);
            if (it == first.end()) // 首次遇到 s[i]
                first[s[i]] = i;
            else if (i - it->second > end - begin) // 更长的子数组
                begin = it->second, end = i;
        }
        return {array.begin() + begin, array.begin() + end};
    }
};

//参考题解
//https://leetcode.cn/problems/find-longest-subarray-lcci/solutions/2160308/tao-lu-qian-zhui-he-ha-xi-biao-xiao-chu-3mb11/

